package com.future;

import java.util.HashMap;
import java.util.Map;

/**
 * Description: 233. 数字 1 的个数
 *
 * @author weiruibai.vendor
 * Date: 2022/10/31 10:45
 */
public class Solution_233 {


    public static void main(String[] args) {
        int n = 199;
        System.out.println(System.currentTimeMillis());
        n = 1234;
        System.out.println(countDigitOn_v2(n));
        //System.out.println(countDigitOn_v3(n));
        System.out.println(System.currentTimeMillis());
        System.out.println("=======================");
        System.out.println(countDigitOn_v2(999));
        System.out.println(countDigitOn_v2(1099));
        System.out.println(countDigitOn_v2(1199)-countDigitOn_v2(1099));
        System.out.println(countDigitOn_v2(1299));
    }

    /**
     * 0～9：1个
     * 10～19：11个
     * 20～29：1个
     * 30～39：1个
     * 40～49：1个
     * 50～59：1个
     * 60～69：1个
     * 70～79：1个
     * 80～89：1个
     * 90～99：1个
     * 总结：0～99 20个
     * 那么
     * 100～199：只考虑百分位的1，个十分位直接来自上面的结果0~99中1的个数，所以：100～199：100+20
     * 同理
     * 200～299：只考虑百分位的1，个十分位直接来自上面的结果0~99中1的个数，所以：200～299：20
     * 300～399：只考虑百分位的1，个十分位直接来自上面的结果0~99中1的个数，所以：300～399：20
     * ....
     * <p>
     * eg: n = 221
     * 方法一：
     * 1、先计算200
     * 0～99：20
     * 100～199：100+20
     * 200：0
     * 所以：0～200: 120+20
     * 2、再计算21
     * 0～9：1
     * 10～19：11
     * 20～21：1
     * 所以：21：13
     * 综上 0～221，出现1的个数为140+23=153
     * <p>
     * 方法二：分别获取个十百千..
     * 1、个位1（看是否还有十位，有的话就计算0～9中1的个数）
     * 0～1：1个，那么
     * 2、十位2（看是否还有百位，有的话就计算0～99中）
     * 0～20：12个
     * 3、百位2（不存在千位，只计算：100～200的）
     * 100～199：100+20个
     * 200：0个
     * 总共：153个
     *
     * @param n
     * @return
     */
    public static int countDigitOn_v3(int n) {
        /**
         * key：9,19,...,99,
         * value：到0～key所有1的个数
         * 格式如：
         * (9,1) 表示0~9，1的个数有1个
         * (99,20) 表示0～99，1的个数有20个
         * ...
         */
        Map<Integer, Integer> map = new HashMap<>();
        int digits = 1;// 记录位数
        // 221
        int ans = 0;
        while (n != 0) {
            int remainder = n % 10;// 余数
            for (int i = 1; i <= remainder; i++) {
                int num = i;
                while (num != 0) {
                    if (num % 10 == 1) {
                        ans++;
                    }
                    num /= 10;
                }
            }
            int divide = n / 10;// divide非0，说明还有更高位
            int pow = (int) Math.pow(10, digits - 1);
            if (divide != 0) {
                /**
                 * 0~9 1的个数
                 * 0～99 1的个数
                 */
                int count = 1;
                int count2 = 0;
                if (digits != 1) {
                    /**
                     * 比如现在是十分位
                     * 那么有10 11 ... 19 10 10个1（只关注当前分位的）
                     * 同时 21 31 41 ... 91 9个1
                     * 比如现在是百分位
                     * 那么有100 101 102 ... 119 100个1（只看百分位）
                     * 同时 201 ... 299
                     *
                     */
                    count2 = (int) Math.pow(10, digits - 1); //
                    count2 += 0;
                }
                Integer orDefault = pow * map.getOrDefault(digits - 1, 1) - 1;
                count += count2 + orDefault;
                map.put(digits, count);
            }
            if (digits > 1) {
                ans += map.get(pow - 1);
            }
            n = divide;
            digits++;
        }
        return ans;
    }

    public static int countDigitOn_v2(int n) {
        if (n <= 0) {
            return 0;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            String val = "" + i;
            if (val.contains("1")) {
                for (int j = 0; j < val.length(); j++) {
                    if (val.charAt(j) == '1') {
                        ans++;
                    }
                }
            }
        }
        return ans;
    }

    /**
     * 超时
     *
     * @param n
     * @return
     */
    public static int countDigitOn_v1(int n) {
        if (n <= 0) {
            return 0;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int val = i;
            while (val != 0) {
                if (val % 10 == 1) {
                    ans++;
                }
                val /= 10;
            }
        }
        return ans;
    }
}
